Maximal Square

LeetCode 221 | Difficulty: Medium

Medium

Problem Description

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

- `m == matrix.length`

- `n == matrix[i].length`

- `1 <= m, n <= 300`

- `matrix[i][j]` is `'0'` or `'1'`.

Topics: Array, Dynamic Programming, Matrix

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 225 ms)

Metric	Value
Runtime	225 ms
Memory	45.7 MB
Date	2022-01-19

Solution

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[,] dp = new int[rows+1, cols+1];
        int max = 0;
        for(int i=1; i<=rows;i++)
        {
            for(int j=1;j<=cols;j++)
            {
                if(matrix[i-1][j-1] == '1')
                {
                    dp[i,j] = 1+ Math.Min(Math.Min(dp[i-1,j], dp[i, j-1]), dp[i-1, j-1]);
                    max = Math.Max(dp[i,j], max);
                }
            }
        }
        return max*max;
        
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.